/**
 * Definition for singly-linked list.
 * */
public class ListNode {
    ListNode next;
    int val;
    ListNode() {}
    ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 }
 
class Solution {
    public ListNode partition(ListNode head, int x) {
        ListNode dummy1 = new ListNode(0); // 小于 x 的链表的虚拟头结点
        ListNode dummy2 = new ListNode(0); // 大于等于 x 的链表的虚拟头结点
        ListNode p1 = dummy1; // 指向小于 x 的链表的尾结点
        ListNode p2 = dummy2; // 指向大于等于 x 的链表的尾结点
        ListNode p = head; // 遍历原链表的指针

        // 遍历原链表
        while(p != null){
            if (p.val < x){
                // 如果当前节点值小于 x，则将其添加到小于 x 的链表
                p1.next = p;
                p1 = p1.next; // p1 指针后移
            }else{
                // 如果当前节点值大于等于 x，则将其添加到大于等于 x 的链表
                p2.next = p;
                p2 = p2.next; // p2 指针后移
            }
            p = p.next; // p 指针后移，遍历下一个节点
        }

        // 此时 p1 指向小于 x 链表的最后一个节点，p2 指向大于等于 x 链表的最后一个节点
        // 需要将 p2.next 置空，防止链表成环
        p2.next = null;
        // 将两个链表连接起来：小于 x 的链表尾部连接大于等于 x 的链表的头部
        p1.next = dummy2.next;
        // 返回小于 x 的链表的头部，即分区后的链表头结点
        return dummy1.next;
    }
}